GermanWikipedia - /page/entry.mu

Micron Document

<!DOCTYPE html>

<title>Präfixcode</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Präfixcode</span></h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p><b>Präfixcode</b> oder <i>präfixfreier Code</i> ist ein Begriff aus der <a href="Kodierungstheorie" title="Kodierungstheorie">Kodierungstheorie</a>.

Als Präfixcode wird ein <a href="Code" title="Code">Code</a> bezeichnet, der die <a href="Fano-Bedingung" title="Fano-Bedingung">Fano-Bedingung</a> erfüllt: Kein Codewort des Codes ist Präfix eines anderen Codewortes. Anders ausgedrückt darf kein Codewort den Beginn eines anderen Codewortes darstellen. Ein Code zum Beispiel mit den Codewörtern {0, 10, 11} erfüllt die Präfix-Eigenschaft, während hingegen der Code mit den Codewörtern {0, 01, 10} sie nicht erfüllt, da „0“ Präfix von „01“ ist.

</p>

<div class="mw-heading mw-heading2"><h2 id="Eigenschaften">Eigenschaften</h2></div>

<ul><li>Bei einem Präfixcode ist eine Nachricht eindeutig in ihre Codewörter zerlegbar</li>

<li>Codewörter können unterschiedlich lang sein</li>

<li>Jeder Präfixcode erfüllt die <a href="Kraft-Ungleichung" title="Kraft-Ungleichung">Kraft-Ungleichung</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Beispiele">Beispiele</h2></div>

<p>Die Objekte A, B, C und D werden mit binären Ziffern dargestellt.

</p>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\rightarrow 0,B\rightarrow 100,C\rightarrow 101,D\rightarrow 11}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/27721685afddc1842be95b0c4ef79f6b21e575d9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:35.218ex; height:2.509ex;" alt="{\displaystyle A\rightarrow 0,B\rightarrow 100,C\rightarrow 101,D\rightarrow 11}" loading="lazy"></span></dd></dl>

<p>Eine unzulässige Codierung wäre die folgende.

</p>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\rightarrow 10,B\rightarrow 100,C\rightarrow 101,D\rightarrow 11}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6956727f8e1f3929400736ad4849baf927828911.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:36.38ex; height:2.509ex;" alt="{\displaystyle A\rightarrow 10,B\rightarrow 100,C\rightarrow 101,D\rightarrow 11}" loading="lazy"></span></dd></dl>

<p>Die Codierung von A kollidiert jeweils mit der von B und von C. Da hierbei beispielsweise CB zu 1011<i>0</i>0 und ADB zu 1011<i>1</i>00 kodiert wird, wird klar, dass ohne die Präfixeigenschaft die Dekodierung eines Codewortes erst einige Ziffern später (oder möglicherweise gar nicht) möglich ist.

</p>

<div class="mw-heading mw-heading3"><h3 id="Telefonnummern">Telefonnummern</h3></div>

<p>Jeder Anschluss muss durch seine Telefonnummer eindeutig identifizierbar sein. Dabei darf es beim Wählprozess nicht dazu kommen, dass es zwischendrin bei einem anderen Teilnehmer klingelt. So beginnt in Deutschland keine andere Telefonnummer außer dem <a href="Notruf" title="Notruf">Notruf</a> mit 112. Ebenso beginnt in keinem Ortsnetz eine Nummer mit 0, damit keine Kollision mit Ortsvorwahlen (oder Sondernummern wie 0800) entsteht. Ähnliche Überlegungen gelten auch für die <a href="Internationale_Vorwahl" class="mw-redirect" title="Internationale Vorwahl">internationale Vorwahl</a>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Huffman-Code">Huffman-Code</h3></div>

<p>Innerhalb des <a href="Huffman-Code" class="mw-redirect" title="Huffman-Code">Huffman-Codes</a> werden Eingabesymbole (beispielsweise die Buchstaben eines Textes) mit unterschiedlich langen binären Ziffernfolgen codiert, deren Länge von der Häufigkeit des zugehörigen Eingabesymbols abhängt. So wird der Speicherverbrauch entsprechend diesen Häufigkeiten optimiert.

Der Huffman-Code ist ein Präfixcode.

</p>

<div class="mw-heading mw-heading3"><h3 id="Fibonacci-Code">Fibonacci-Code</h3></div>

<p>Der <a href="Fibonacci-Kode" class="mw-redirect" title="Fibonacci-Kode">Fibonacci-Code</a> ist ein universeller Präfixcode für die natürlichen Zahlen.

</p>

<div class="mw-heading mw-heading3"><h3 id="Morse-Code">Morse-Code</h3></div>

<p>Der <a href="Morsezeichen" class="mw-redirect" title="Morsezeichen">Morse-Code</a> ist von Haus aus kein Präfixcode, da beispielsweise A (kurz-lang) ein Präfix von L (kurz-lang-kurz-kurz) ist. Erst durch das Einfügen von Pausen (im Prinzip ein drittes Symbol neben kurz und lang) zwischen Buchstaben wird die Nachricht eindeutig dekodierbar, z. B. kurz-lang-Pause-kurz-kurz = AI, kurz-lang-kurz-Pause-kurz = RE.

</p>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>Thomas H. Cormen, <a href="Charles_E._Leiserson" title="Charles E. Leiserson">Charles E. Leiserson</a>, <a href="Ronald_L._Rivest" title="Ronald L. Rivest">Ronald L. Rivest</a>: <cite style="font-style:italic">Introduction to Algorithms</cite>. 2. Auflage. M.I.T. Press u. a., Cambridge MA [u. a.] 2001, ISBN 0-262-03293-7.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Pr%C3%A4fixcode&rft.au=Thomas+H.+Cormen%2C+Charles+E.+Leiserson%2C+Ronald+L.+Rivest&rft.btitle=Introduction+to+Algorithms&rft.date=2001&rft.edition=2.&rft.genre=book&rft.isbn=0262032937&rft.place=Cambridge+MA+%5Bu.+a.%5D&rft.pub=M.I.T.+Press+u.+a." style="display:none"> </span></li>

<li>Ralph-Hardo Schulz: <cite style="font-style:italic">Codierungstheorie. Eine Einführung</cite>. 2. aktualisierte und erweiterte Auflage. Vieweg+Teubner Verlag, Wiesbaden 2003, ISBN 3-528-16419-0.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Pr%C3%A4fixcode&rft.au=Ralph-Hardo+Schulz&rft.btitle=Codierungstheorie.+Eine+Einf%C3%BChrung&rft.date=2003&rft.edition=2.+aktualisierte+und+erweiterte&rft.genre=book&rft.isbn=3528164190&rft.place=Wiesbaden&rft.pub=Vieweg%2BTeubner+Verlag" style="display:none"> </span></li>

<li>Herbert Klimant, Rudi Piotraschke, Dagmar Schönfeld: <cite style="font-style:italic">Informations- und Kodierungstheorie</cite>. 3. überarbeitete und erweiterte Auflage. Vieweg+Teubner Verlag, Wiesbaden 2006, ISBN 3-8351-0042-4 (<i>Lehrbuch Informatik</i>).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Pr%C3%A4fixcode&rft.au=Herbert+Klimant%2C+Rudi+Piotraschke%2C+Dagmar+Sch%C3%B6nfeld&rft.btitle=Informations-+und+Kodierungstheorie&rft.date=2006&rft.edition=3.+%C3%BCberarbeitete+und+erweiterte&rft.genre=book&rft.isbn=3835100424&rft.place=Wiesbaden&rft.pub=Vieweg%2BTeubner+Verlag" style="display:none"> </span></li></ul></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2020-04-23" href="https://de.wikipedia.org/wiki/?title=Pr%C3%A4fixcode&oldid=199193629">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>